package arrAndstr;

/*
    200. 岛屿数量
    如何避免使用额外的数组记录以遍历的格子？
        在本数组上进行修改，如原来为0、1，把原来为1且遍历过的改为2
 */
public class T200 {

    private static int landNum = 0;
    private static int xMax = 0;
    private static int yMax = 0;

    public static int numIslands(char[][] grid) {
        xMax = grid.length;
        yMax = grid[0].length;

        for (int x = 0; x < grid.length; x++) {
            for (int y = 0; y < grid[x].length; y++) {
                // 第一次到某一个陆地上，landNum++，并遍历修改整块陆地
                if (grid[x][y] == '1') {
                    landNum++;
                    numIslands(grid, x, y);
                }
            }
        }

        return landNum;
    }

    private static void numIslands(char[][] grid, int x, int y) {
        if (!inGrid(x, y) || grid[x][y]!='1') return;

        grid[x][y] = '2';
        numIslands(grid, x-1, y);
        numIslands(grid, x+1, y);
        numIslands(grid, x, y-1);
        numIslands(grid, x, y+1);
    }

    private static boolean inGrid(int x, int y) {
        return x>=0 && x<xMax && y>=0 && y<yMax;
    }


    public static void main(String[] args) {
        char[][] grid1 = {
                {'1','1','1','1','0'},
                {'1','1','0','1','0'},
                {'1','1','0','0','0'},
                {'0','0','0','0','0'}
        };
        System.out.println(numIslands(grid1)); // 输出: 1

        char[][] grid2 = {
                {'1','1','0','0','0'},
                {'1','1','0','0','0'},
                {'0','0','1','0','0'},
                {'0','0','0','1','1'}
        };
        System.out.println(numIslands(grid2)); // 输出: 3
    }

}
